// @algorithm @lc id=300 lang=cpp 
// @title longest-increasing-subsequence


// #define print(...)
// @test([10,9,2,5,3,7,101,18])=4
// @test([0,1,0,3,2,3])=4
// @test([7,7,7,7,7,7,7])=1
#define USE_DP
class Solution {
public:
#ifdef USE_DP // 动态规则
    int lengthOfLIS(vector<int>& nums) {
        if(nums.empty()) return 0;
        vector<int> dp(nums.size(), 1);
        dp[0] = 1;
        for(int i=1; i<nums.size(); i++){
            for(int j=0; j<i; j++)
                if(nums[j]<nums[i] && dp[i] < dp[j]+1)
                    dp[i] = dp[j] + 1;
        }
        return *max_element(dp.begin(), dp.end());
    }
#else // 贪心
    int lengthOfLIS(vector<int>& nums) {
        vector<int> asc;
        for(auto & a : nums){
            auto ax = lower_bound(asc.begin(), asc.end(), a);
            if(ax == asc.end())
                asc.push_back(a);
            else
                *ax = a;
        }
        return asc.size();
    }
#endif
};